#include<iostream>
#include<cstring>
#include<pthread.h>
#include<arm_neon.h>
#include<sys/time.h>
using namespace std;
const int N = 10000;
int g[N][N], dist[N], st[N];
int min_dist, vertex;

int NUM_THREADS = 7;
pthread_barrier_t get_min;
pthread_barrier_t update;
pthread_mutex_t mutex;
pthread_t handles[8];
threadParam_t params[8];

void* threadFunc(void* param) {
	threadParam_t* p = (threadParam_t*)param;
	int t_id = p->t_id;
	int n = p->n;
	for (int i = 0; i < n - 1; ++i) {
		int m_vertex = -1;
		for (int j = t_id; j <= n; j += NUM_THREADS)
			if (!st[j] && (m_vertex == -1 || dist[m_vertex] > dist[j])) {
				m_vertex = j;

			}
		pthread_mutex_lock(&mutex);
		if (m_vertex != -1 && min_dist > dist[m_vertex]) {
			min_dist = dist[m_vertex];
			vertex = m_vertex;
		}
		pthread_mutex_unlock(&mutex);
		pthread_barrier_wait(&get_min);
		st[vertex] = 1;
		min_dist = 0x3f3f3f3f;
		int d = n / NUM_THREADS;
		int m_start = 1 + (t_id - 1) * d;
		int m_end = min(t_id * d, n);
		int j = m_start;
		for (j= m_start; j + 4 <= m_end; j += 4) {
			int32x4_t t1 = vld1q_s32(&dist[j]);
			int32x4_t t2 = vld1q_s32(&g[vertex][j]);
			int32x4_t t3 = vmovq_n_s32(dist[vertex]);
			t2 = vaddq_s32(t2, t3);
			t1 = vminq_s32(t1, t2);
			vst1q_s32(&dist[j], t1);
		}
		for (int k=j; k <= m_end; ++k)
			dist[k] = min(dist[k], dist[vertex] + g[vertex][k]);
		pthread_barrier_wait(&update);
	}
	return NULL;
}
int main(int argc,char** args) {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)g[i][i] = 0;
	memset(dist, 0x3f, sizeof dist);
	memset(g, 0x3f, sizeof g);
	for (int i = 0; i < m; ++i) {
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		if (c > g[a][b] || a == b)continue;
		g[a][b] = c;
	}
	dist[1] = 0;
	min_dist = 0x3f3f3f3f;
	pthread_barrier_init(&get_min, NULL, NUM_THREADS);
	pthread_barrier_init(&update, NULL, NUM_THREADS);
	pthread_mutex_init(&mutex, NULL);
NUM_THREADS=args[1][0]-'0';
   struct timeval t1,t2;
    double time=0.0;
	gettimeofday(&t1,NULL);
	////
	for (int i = 1; i <= NUM_THREADS; ++i) {
		params[i].n = n;
		params[i].t_id = i;
		pthread_create(&handles[i], NULL, threadFunc, &params[i]);
	}
	for (int i = 1; i <= NUM_THREADS; ++i)
		pthread_join(handles[i], NULL);
	////

	////
	dijkstra(n);
	////
	gettimeofday(&t2,NULL);
	time=(double)(t2.tv_sec-t1.tv_sec)*1000.0 + (double)(t2.tv_usec-t1.tv_usec)/1000.0;
	cout<< time;
}